package leetcode.editor.cn;

public class Solution1043 {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int length = arr.length;
        int[] dp = new int[length];
        for (int i=0;i<length;i++){
            int doMax = arr[i];
            for (int j=1;j<=k&&i-j+1>=0;j++){
                doMax= Math.max(doMax, arr[i-j+1]);
                if (i-j>=0){
                    dp[i] = Math.max(dp[i], dp[i-j]+j*doMax);
                }else {
                    dp[i] = Math.max(dp[i], j*doMax);
                }
            }
        }
        return dp[length-1];
    }
}
